package simple;

import java.util.*;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/10/18 12:13
 */
public class No350_两个数组的交集II {
    public static void main(String[] args) {
        Solution350 solution350 = new Solution350();
        int[] nums1 = new int[]{2, 2, 5, 5, 9};
        int[] nums2 = new int[]{2, 5, 5, 7, 8, 9};
        int[] intersect = solution350.intersect(nums1, nums2);
    }
}

class Solution350 {
    public int[] intersect(int[] nums1, int[] nums2) {
        //哈希
        //(数,个数)
        Map<Integer, Integer> map = new HashMap<>();
        //初始化map
        for (int data : nums1) {
            addMapKeys(map, data);
        }

        List<Integer> list = new ArrayList<>();

        //第二个nums里面查找
        for (int data : nums2) {
            if (map.get(data) == null || map.get(data) == 0) {
                continue;
            }
            list.add(data);
            //map.get(data) == 0??
            map.put(data, map.get(data) - 1);
        }

        //转回数组
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }

        return res;
    }

    public void addMapKeys(Map<Integer, Integer> map, int key) {
        if (map.get(key) == null) {
            map.put(key, 1);
        } else {
            map.put(key, map.get(key) + 1);
        }
    }
}


    //public int[] intersect(int[] nums1, int[] nums2) {
    //
    //    if (nums1.length == 0 || nums2.length == 0) {
    //        return new int[]{};
    //    }
    //
    //    //排序
    //    Arrays.sort(nums1);
    //    Arrays.sort(nums2);
    //
    //    //指针初始化
    //    int red = 0;
    //    int green = 0;
    //
    //    int checkRed = nums1[red];
    //    int checkGreen = nums2[green];
    //
    //    List<Integer> list = new ArrayList<>();
    //
    //    while (red < nums1.length && green < nums2.length) {
    //        //指针相同,同时移动
    //        while (checkRed == checkGreen) {
    //            list.add(checkGreen);
    //            red++;
    //            green++;
    //            if (red == nums1.length || green == nums2.length) {
    //                break;
    //            }
    //            checkRed = nums1[red];
    //            checkGreen = nums2[green];
    //        }
    //
    //        while (checkRed < checkGreen) {
    //            red++;
    //            if (red == nums1.length) {
    //                break;
    //            }
    //            checkRed = nums1[red];
    //        }
    //
    //        while (checkRed > checkGreen) {
    //            green++;
    //            if (green == nums2.length) {
    //                break;
    //            }
    //            checkGreen = nums2[green];
    //        }
    //    }
    //
    //    //变回数组
    //    int[] res = new int[list.size()];
    //    for (int i = 0; i < list.size(); i++) {
    //        res[i] = list.get(i);
    //    }
    //    return res;
    //
    //}


